home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / DJLSR106.ARJ / FIX.CC < prev    next >
C/C++ Source or Header  |  1992-03-30  |  13KB  |  600 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3. Copyright (C) 1989 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18. //
  19. // Fix.cc : variable length fixed point data type class functions
  20. //
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation "Fix.h"
  24. #endif
  25. #include <Fix.h>
  26. #include <std.h>
  27. #include <_Obstack.h>
  28. #include <AllocRing.h>
  29.  
  30. // default parameters
  31.  
  32. uint16 Fix_default_length = 16;
  33. int    Fix_default_print_width = 8;
  34.  
  35. Fix_peh Fix_overflow_handler = Fix_overflow_saturate;
  36.  
  37. _Frep _Frep_0    = { 16, 1, 1, { 0 } };
  38. _Frep _Frep_m1    = { 16, 1, 1, { 0x8000 } };
  39. _Frep _Frep_quotient_bump = { 16, 1, 1, { 0x4000 } };
  40.  
  41. // error handling
  42.  
  43. void default_Fix_error_handler(const char* msg)
  44. {
  45.   cerr << "Fix: " << msg << "\n";
  46.   abort();
  47. }
  48.  
  49. void default_Fix_range_error_handler(const char* msg)
  50. {
  51.   cerr << "Fix: range error in " << msg << "\n";
  52.   //abort();
  53. }
  54.  
  55. one_arg_error_handler_t 
  56.   Fix_error_handler = default_Fix_error_handler,
  57.   Fix_range_error_handler = default_Fix_range_error_handler;
  58.  
  59. one_arg_error_handler_t set_Fix_error_handler(one_arg_error_handler_t f)
  60. {
  61.   one_arg_error_handler_t old = Fix_error_handler;
  62.   Fix_error_handler = f;
  63.   return old;
  64. }
  65.  
  66. one_arg_error_handler_t set_Fix_range_error_handler(one_arg_error_handler_t f)
  67. {
  68.   one_arg_error_handler_t old = Fix_range_error_handler;
  69.   Fix_range_error_handler = f;
  70.   return old;
  71. }
  72.  
  73. void Fix::error(const char* msg)
  74. {
  75.   (*Fix_error_handler)(msg);
  76. }
  77.  
  78. void Fix::range_error(const char* msg)
  79. {
  80.   (*Fix_range_error_handler)(msg);
  81. }
  82.  
  83. // _Frep allocation and initialization functions
  84.  
  85. static inline _Fix _new_Fix(uint16 len)
  86. {
  87.   int siz = (((uint32 )len + 15) >> 4);
  88.   if (siz <= 0) siz = 1;
  89.   unsigned int allocsiz = (sizeof(_Frep) + (siz - 1) * sizeof(uint16));
  90.   _Fix z = (_Fix)(new char[allocsiz]);
  91.   bzero(z, allocsiz);
  92.   z->len = len;
  93.   z->siz = siz;
  94.   z->ref = 1;
  95.   return z;
  96. }
  97.  
  98. _Fix new_Fix(uint16 len)
  99. {
  100.   return _new_Fix(len);
  101. }
  102.  
  103. _Fix new_Fix(uint16 len, _Fix x)
  104. {
  105.   _Fix z = _new_Fix(len);
  106.   return copy(x,z);
  107. }
  108.  
  109. _Fix new_Fix(uint16 len, double d)
  110. {
  111.   _Fix z = _new_Fix(len);
  112.  
  113.   if ( d == _Fix_max_value )
  114.   {
  115.     z->s[0] = 0x7fff;
  116.     for ( int i=1; i < z->siz; i++ )
  117.       z->s[i] = 0xffff;
  118.   }
  119.   else if ( d < _Fix_min_value || d > _Fix_max_value )
  120.     (*Fix_range_error_handler)("declaration");
  121.   else
  122.   {
  123.     if (d < 0)
  124.       d += 2.0;
  125.     d *= 32768;
  126.     for ( int i=0; i < z->siz; i++ )
  127.     {
  128.       z->s[i] = (uint16 )d;
  129.       d -= z->s[i];
  130.       d *= 65536;
  131.     }
  132.     if ( d >= 32768 )
  133.       z->s[z->siz-1]++;
  134.   }
  135.   mask(z);
  136.   return z;
  137. }
  138.  
  139. // convert to a double 
  140.  
  141. double value(Fix& x)
  142. { 
  143.   double d = 0.0;
  144.   for ( int i=x.rep->siz-1; i >= 0; i-- )
  145.   {
  146.     d += x.rep->s[i];
  147.     d *= 1./65536.;
  148.   }
  149.   d *= 2.;
  150.   return d < 1. ? d : d - 2.;
  151. }
  152.  
  153. // extract mantissa to Integer
  154.  
  155. Integer mantissa(Fix& x)
  156. {
  157.   Integer a = 1, b=1;
  158.   for ( int i=0; i < x.rep->siz; i++ )
  159.   {
  160.     a = (a << 16) + x.rep->s[i];
  161.     b <<= 16;
  162.   }
  163.   return a-b;
  164. }
  165.  
  166. // comparison functions
  167.   
  168. inline static int docmp(uint16* x, uint16* y, int siz)
  169. {
  170.   int diff = (int16 )*x - (int16 )*y;
  171.   while ( --siz && !diff )
  172.     diff = (int32 )(uint32 )*++x - (int32 )(uint32 )*++y;
  173.   return diff;
  174. }
  175.  
  176. inline static int docmpz(uint16* x, int siz)
  177. {
  178.   while ( siz-- )
  179.     if ( *x++ ) return 1;
  180.   return 0;
  181. }
  182.  
  183. int compare(_Fix x, _Fix y)
  184. {
  185.   if ( x->siz == y->siz )
  186.     return docmp(x->s, y->s, x->siz);
  187.   else
  188.   {
  189.     int r;
  190.     _Fix longer, shorter;
  191.     if ( x->siz > y->siz )
  192.     {
  193.       longer = x;
  194.       shorter = y;
  195.       r = 1;
  196.     }
  197.     else
  198.     {
  199.       longer = y;
  200.       shorter = x;
  201.       r = -1;
  202.     }
  203.     int diff = docmp(x->s, y->s, shorter->siz);
  204.     if ( diff )
  205.       return diff;
  206.     else if ( docmpz(&longer->s[shorter->siz], longer->siz-shorter->siz) )
  207.       return r;
  208.     else
  209.       return 0;
  210.   }
  211. }
  212.  
  213. // arithmetic functions
  214.  
  215. _Fix add(_Fix x, _Fix y, _Fix r)
  216. {
  217.   uint16 xsign = x->s[0], ysign = y->s[0];
  218.   _Fix longer, shorter;
  219.   if ( x->len >= y->len )
  220.     longer = x, shorter = y;
  221.   else
  222.     longer = y, shorter = x;
  223.   if ( r == NULL )
  224.     r = new_Fix(longer->len);
  225.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  226.     r->s[i] = 0;
  227.   for ( ; i >= shorter->siz; i-- )
  228.     r->s[i] = longer->s[i];
  229.   uint32 sum = 0, carry = 0;
  230.   for ( ; i >= 0; i-- )
  231.   {
  232.     sum = carry + (uint32 )x->s[i] + (uint32 )y->s[i];
  233.     carry = sum >> 16;
  234.     r->s[i] = sum;
  235.   }
  236.   if ( (xsign ^ sum) & (ysign ^ sum) & 0x8000 )
  237.     (*Fix_overflow_handler)(r);
  238.   return r;
  239. }
  240.  
  241. _Fix subtract(_Fix x, _Fix y, _Fix r)
  242. {
  243.   uint16 xsign = x->s[0], ysign = y->s[0];
  244.   _Fix longer, shorter;
  245.   if ( x->len >= y->len )
  246.     longer = x, shorter = y;
  247.   else
  248.     longer = y, shorter = x;
  249.   if ( r == NULL )
  250.     r = new_Fix(longer->len);
  251.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  252.     r->s[i] = 0;
  253.   for ( ; i >= shorter->siz; i-- )
  254.     r->s[i] = (longer == x ? x->s[i] : -y->s[i]);
  255.   int16 carry = 0;
  256.   uint32 sum = 0;
  257.   for ( ; i >= 0; i-- )
  258.   {
  259.     sum = (int32 )carry + (uint32 )x->s[i] - (uint32 )y->s[i];
  260.     carry = sum >> 16;
  261.     r->s[i] = sum;
  262.   }
  263.   if ( (xsign ^ sum) & (~ysign ^ sum) & 0x8000 )
  264.     (*Fix_overflow_handler)(r);
  265.   return r;
  266. }
  267.  
  268. _Fix multiply(_Fix x, _Fix y, _Fix r)
  269. {
  270.   if ( r == NULL )
  271.     r = new_Fix(x->len + y->len);
  272.   int xsign = x->s[0] & 0x8000,
  273.     ysign = y->s[0] & 0x8000;
  274.   Fix X(x->len), Y(y->len);
  275.   if ( xsign )
  276.     x = negate(x,X.rep);
  277.   if ( ysign )
  278.     y = negate(y,Y.rep);
  279.   for ( int i=0; i < r->siz; i++ )
  280.     r->s[i] = 0;
  281.   for ( i=x->siz-1; i >= 0; i-- )
  282.   {
  283.     uint32 carry = 0;
  284.     for ( int j=y->siz-1; j >= 0; j-- ) 
  285.     {
  286.       int k = i + j + 1;
  287.       uint32 a = (uint32 )x->s[i] * (uint32 )y->s[j];
  288.       uint32 b = ((a << 1) & 0xffff) + carry;
  289.       if ( k < r->siz )
  290.       {
  291.     b += r->s[k];
  292.         r->s[k] = b;
  293.       }
  294.       if ( k < r->siz + 1 )
  295.         carry = (a >> 15) + (b >> 16);
  296.     }
  297.     r->s[i] = carry;
  298.   }
  299.   if ( xsign != ysign )
  300.     negate(r,r);
  301.   return r;
  302. }
  303.  
  304. _Fix multiply(_Fix x, int y, _Fix r)
  305. {
  306.   if ( y != (int16 )y )
  307.     (*Fix_range_error_handler)("multiply by int -- int too large");
  308.   if ( r == NULL )
  309.     r = new_Fix(x->len);
  310.   for ( int i=r->siz-1; i >= x->siz; i-- )
  311.     r->s[i] = 0;
  312.   int32 a, carry = 0;
  313.   for ( ; i > 0; i-- )
  314.   {
  315.     a = (int32 )(uint32 )x->s[i] * y + carry;
  316.     r->s[i] = a;
  317.     carry = a >> 16;        // assumes arithmetic right shift
  318.   }
  319.   a = (int32 )(int16 )x->s[0] * y + carry;
  320.   r->s[0] = a;
  321.   a &= 0xffff8000L;
  322.   if ( a != 0xffff8000L && a != 0L ) {
  323.     r->s[0] = 0x8000 ^ x->s[0] ^ y;
  324.     (*Fix_overflow_handler)(r);
  325.   }
  326.   return r;
  327. }
  328.  
  329. _Fix divide(_Fix x, _Fix y, _Fix q, _Fix r)
  330. {
  331.   int xsign = x->s[0] & 0x8000, 
  332.     ysign = y->s[0] & 0x8000;
  333.   if ( q == NULL )
  334.     q = new_Fix(x->len);
  335.   copy(&_Frep_0,q);
  336.   if ( r == NULL )
  337.     r = new_Fix(x->len + y->len - 1);
  338.   if ( xsign )
  339.     negate(x,r);
  340.   else
  341.     copy(x,r);
  342.   Fix Y(y->len);
  343.   y = ( ysign ? negate(y,Y.rep) : copy(y,Y.rep) );
  344.   if ( !compare(y) )
  345.     (*Fix_range_error_handler)("division -- division by zero");
  346.   else if ( compare(x,y) >= 0 )
  347.     if ( compare(x,y) == 0 && (xsign ^ ysign) != 0 )
  348.     {
  349.       copy(&_Frep_m1,q);
  350.       copy(&_Frep_0,r);
  351.     }
  352.     else
  353.       (*Fix_range_error_handler)("division");
  354.   else
  355.   {
  356.     _Fix t;
  357.     Fix S(r->len),
  358.       W(q->len,&_Frep_quotient_bump);
  359.     for ( int i=1; i < q->len; i++ )
  360.     {
  361.       shift(y,-1,y);
  362.       subtract(r,y,S.rep);
  363.       int s_status = compare(S.rep);
  364.       if ( s_status == 0 ) 
  365.       {
  366.     t = r, r = S.rep, S.rep = t;
  367.     break;
  368.       }
  369.       else if ( s_status > 0 )
  370.       {
  371.     t = r, r = S.rep, S.rep = t;
  372.     add(q,W.rep,q);
  373.       }
  374.       shift(W.rep,-1,W.rep);
  375.     }
  376.     if ( xsign ^ ysign )
  377.       negate(q,q);
  378.   }
  379.   return q;
  380. }
  381.  
  382. _Fix shift(_Fix x, int y, _Fix r)
  383. {
  384.   if ( y == 0 )
  385.     return x;
  386.   else if ( r == NULL )
  387.     r = new_Fix(x->len);
  388.  
  389.   int ay = abs((long) y),
  390.     ayh = ay >> 4,
  391.     ayl = ay & 0x0f;
  392.   int xl, u, ilow, ihigh;
  393.   uint16 *rs, *xsl, *xsr;
  394.  
  395.   if ( y > 0 )
  396.   {
  397.     rs = r->s;
  398.     xsl = x->s + ayh;
  399.     xsr = xsl + 1;
  400.     xl = ayl;
  401.     u = 1;
  402.     ihigh = x->siz - ayh - 1;
  403.     ilow = 0;
  404.   }
  405.   else
  406.   {
  407.     rs = &r->s[r->siz - 1];
  408.     xsr = &x->s[r->siz - 1] - ayh;
  409.     xsl = xsr - 1;
  410.     xl = 16 - ayl;
  411.     u = -1;
  412.     ihigh = r->siz - ayh - 1;
  413.     ilow = ihigh - x->siz;
  414.   }
  415.  
  416.   int xr = 16 - xl;
  417.   uint16 xrmask = 0xffffL >> xr;
  418.   for ( int i=0; i < ilow; i++, rs+=u, xsl+=u, xsr+=u )
  419.     *rs = 0;
  420.   for ( ; i < ihigh; i++, rs+=u, xsl+=u, xsr+=u )
  421.     *rs = (*xsl << xl) + ((*xsr >> xr) & xrmask);
  422.   *rs = (y > 0 ? (*xsl << xl) : ((*xsr >> xr) & xrmask));
  423.   rs += u;
  424.   for ( ; ++i < r->siz; rs+=u )
  425.     *rs = 0;
  426.   return r;
  427. }
  428.  
  429. _Fix negate(_Fix x, _Fix r)
  430. {
  431.   if ( r == NULL )
  432.     r = new_Fix(x->len);
  433.   uint32 carry = 1;
  434.   for ( int i=r->siz-1; i >= x->siz; i-- )
  435.     r->s[i] = 0;
  436.   for ( ; i >= 0; i-- )
  437.   {
  438.     uint32 a = (uint16 )~x->s[i] + carry;    // bug work-around
  439.     r->s[i] = a;
  440.     carry = a >> 16;
  441.   }
  442.   return r;
  443. }
  444.  
  445. // io functions
  446.  
  447. Fix atoF(const char* a, int len)
  448. {
  449.   return Fix(len,atof(a));
  450. }
  451.  
  452. extern AllocRing _libgxx_fmtq;
  453.  
  454. char* Ftoa(Fix& x, int width)
  455. {
  456.   int wrksiz = width + 2;
  457.   char *s = (char *) _libgxx_fmtq.alloc(wrksiz);
  458.   char format[100];
  459.   double val = value(x);
  460.   if (val < 0)
  461.     sprintf(format,"%%%d.%dlf",width-2,width-3);
  462.   else
  463.     sprintf(format," %%%d.%dlf",width-2,width-3);
  464.   sprintf(s,format,val);
  465.   return s;
  466. }
  467.  
  468. extern Obstack _libgxx_io_ob;
  469.  
  470. Fix Fix::operator %= (int y)
  471. {
  472.   Fix r((int )rep->len + y, *this); return *this = r;
  473. }
  474.  
  475. istream& operator >> (istream& s, Fix& y)
  476. {
  477.   int got_one = 0;
  478. #ifdef _OLD_STREAMS
  479.   if (!s.good())
  480.   {
  481.     return s;
  482.   }
  483. #else
  484.   if (!s.ipfx(0))
  485.   {
  486.     s.set(ios::failbit); // Redundant if using GNU iostreams.
  487.     return s;
  488.   }
  489. #endif
  490.  
  491.   char sign = 0, point = 0;
  492.   char ch;
  493.   s >> ws;
  494.   if (!s.good())
  495.   {
  496.     s.set(_fail);
  497.     return s;
  498.   }
  499.   while (s.get(ch))
  500.   {
  501.     if (ch == '-')
  502.     {
  503.       if (sign == 0)
  504.       {
  505.         sign = 1;
  506.         _libgxx_io_ob.grow(ch);
  507.       }
  508.       else
  509.         break;
  510.     }
  511.     if (ch == '.')
  512.     {
  513.       if (point == 0)
  514.       {
  515.         point = 1;
  516.         _libgxx_io_ob.grow(ch);
  517.       }
  518.       else
  519.         break;
  520.     }
  521.     else if (ch >= '0' && ch <= '9')
  522.     {
  523.       got_one = 1;
  524.       _libgxx_io_ob.grow(ch);
  525.     }
  526.     else
  527.       break;
  528.   }
  529.   char * p = (char*)(_libgxx_io_ob.finish(0));
  530.   if (s.good())
  531.     s.putback(ch);
  532.   if (!got_one)
  533.     s.set(_fail);
  534.   else
  535.     y = atoF(p);
  536.   _libgxx_io_ob.free(p);
  537.   return s;
  538. }
  539.  
  540. void show(Fix& x)
  541. {
  542.   cout << "len = " << x.rep->len << "\n";
  543.   cout << "siz = " << x.rep->siz << "\n";
  544.   cout << "ref = " << x.rep->ref << "\n";
  545.   cout << "man = " << Itoa(mantissa(x),16,4*x.rep->siz) << "\n";
  546.   cout << "val = " << value(x) << "\n";
  547. }
  548.  
  549. // parameter setting operations
  550.  
  551. Fix_peh set_overflow_handler(Fix_peh new_handler) {
  552.   Fix_peh old_handler = Fix_overflow_handler;
  553.   Fix_overflow_handler = new_handler;
  554.   return old_handler;
  555. }
  556.  
  557. int Fix_set_default_length(int newlen)
  558. {
  559.   uint16 oldlen = Fix_default_length;
  560.   if ( newlen < _Fix_min_length || newlen > _Fix_max_length )
  561.     (*Fix_error_handler)("illegal length in Fix_set_default_length");
  562.   Fix_default_length = newlen;
  563.   return oldlen;
  564. }
  565.  
  566. // overflow handlers
  567.  
  568. void Fix_overflow_saturate(_Fix& r) {
  569.   if ( (int16 )r->s[0] > 0 ) 
  570.   {
  571.     r->s[0] = 0x8000;
  572.     for ( int i=1; i < r->siz; i++ )
  573.       r->s[i] = 0;
  574.   }
  575.   else
  576.   {
  577.     r->s[0] = 0x7fff;
  578.     for ( int i=1; i < r->siz; i++ )
  579.       r->s[i] = 0xffff;
  580.     mask(r);
  581.   }
  582. }
  583.  
  584. void Fix_overflow_wrap(_Fix& r) {}
  585.  
  586. void Fix_overflow_warning_saturate(_Fix& r) {
  587.   Fix_overflow_warning(r);
  588.   Fix_overflow_saturate(r);
  589. }
  590.  
  591. void Fix_overflow_warning(_Fix& r) {
  592.   cerr << "Fix: overflow warning\n"; 
  593. }
  594.  
  595. void Fix_overflow_error(_Fix& r) {
  596.   cerr << "Fix: overflow error\n"; 
  597.   abort();
  598. }
  599.  
  600.